package scales.utils.collection
import annotation.tailrec
import scales.utils.Equiv
import scalaz._
import Scalaz._
object ListSet {
def empty[A : Equal] = new ListSet[A]
def apply[A : Equal]( a : A*) = empty[A] ++ (a)
}
@serializable
class ListSet[A : Equal](val plusFast : Boolean = false) extends Iterable[A]{ self =>
val equal = implicitly[Equal[A]]
def ++( other : Traversable[A] ) = other.foldLeft(this)(_ + _)
def --( other : Traversable[A] ) = other.foldLeft(this)(_ - _)
def --[B,C]( other : Traversable[B] )(implicit equiv: Equiv[C], viewA: A => C, viewB: B => C) = other.foldLeft(this)(_ - _)
override def size: Int = 0
override def isEmpty: Boolean = true;
def contains(elem: A): Boolean = false
def empty = new ListSet[A]
def contains[B,C]( b : B )(implicit equiv: Equiv[C], viewA: A => C, viewB: B => C) = false
def apply[B,C]( b : B )(implicit equiv: Equiv[C], viewA: A => C, viewB: B => C) : Option[A] = None
def + (elem: A): ListSet[A] = new Node(elem)
def unsafePlus(e: A): ListSet[A] = new Node(e)
def - (elem: A): ListSet[A] = this
def -[B,C]( b : B )(implicit equiv: Equiv[C], viewA: A => C, viewB: B => C) : ListSet[A] = this
private[ListSet] def unchecked_outer: ListSet[A] =
throw new NoSuchElementException("Empty ListSet has no outer pointer")
def iterator: Iterator[A] = new Iterator[A] {
var that: ListSet[A] = self;
def hasNext = !that.isEmpty;
def next: A =
if (!hasNext) throw new NoSuchElementException("next on empty iterator")
else { val res = that.elem; that = that.next; res }
}
protected def elem: A = throw new NoSuchElementException("Set has no elements");
protected def next: ListSet[A] = throw new NoSuchElementException("Next of an empty set");
protected def newThis(a : A) = new Node(a)
@serializable
protected class Node(override protected val elem: A) extends ListSet[A] {
override private[ListSet] def unchecked_outer = self
override def size = {
@tailrec def sizeInternal(n: ListSet[A], acc: Int): Int =
if (n.isEmpty) acc
else sizeInternal(n.unchecked_outer, acc + 1)
sizeInternal(this, 0)
}
override def isEmpty: Boolean = false
override def contains(e: A) = {
@tailrec def containsInternal(n: ListSet[A], e: A): Boolean =
!n.isEmpty && (equal.equal(e, n.elem) || containsInternal(n.unchecked_outer, e))
containsInternal(this, e)
}
override def contains[B,C]( e : B )(implicit equiv: Equiv[C], viewA: A => C, viewB: B => C) = {
@tailrec def containsInternal(n: ListSet[A], e: B): Boolean =
!n.isEmpty && (
equiv(e, n.elem)
|| containsInternal(n.unchecked_outer, e) )
containsInternal(this, e)
}
override def apply[B,C]( e : B )(implicit equiv: Equiv[C], viewA: A => C, viewB: B => C) : Option[A] = {
@tailrec def applyInternal(n : ListSet[A], e : B) : Option[A] =
if (n.isEmpty)
None
else
if (equiv(e, n.elem))
Some(n.elem)
else
applyInternal(n.unchecked_outer, e)
applyInternal(this, e)
}
override def +(e: A): ListSet[A] = if (contains(e)) this.-(e).newThis(e) else new Node(e)
override def unsafePlus(e: A): ListSet[A] = new Node(e)
override def -(e: A): ListSet[A] = if (equal.equal(e, elem)) self else {
val tail = self - e; new tail.Node(elem)
}
override def -[B,C]( e : B )(implicit equiv: Equiv[C], viewA: A => C, viewB: B => C) : ListSet[A] =
if (equiv(e, elem)) self else {
val tail = self - e; new tail.Node(elem)
}
override protected def newThis(a : A) = new Node(a)
override protected def next: ListSet[A] = self
}
}